class Solution {
public:
    int integerBreak(int n) {
        vector <int> a(n + 1);
        for (int i = 2; i <= n; i++) {
            int max1 = 0;
            for (int j = 1; j < i; j++) {
                max1= max(max1, max(j * (i - j), j * a[i - j]));
            }
            a[i] = max1;
        }
        return a[n];
    }
};
